/**
 * 给定数组nums与固定值m，求nums中所有大小为m的子序列的首尾元素之积的最大值
 * 固定子序列的结尾，只需要枚举开头即可。
 * 注意到乘积最大则开头必然取最小值或者最大值（因为有负数）
 * for i in [m-1, n-1]:
 *     令 right = i - (m - 1)
 *     则取出[0, right]区间的最大与最小值
 *     分别与nums[i]相乘更新答案即可
 * 求区间最值使用ST表。
 * 实际上可以在枚举i的时候顺便维护区间最值。 
 */

template<typename IT = vector<int>::const_iterator>
struct SparseTable{

using T = pair<int, int>;
using vt = vector<T>; 
using vvt = vector<vt>;

SparseTable() = delete;

IT head;
vvt data;

/// 从s开始的n个数，作为原始数组，建立ST表，索引从0开始
/// 整个ST期间，原始数组的内容不能改变
SparseTable(IT begin, int n):head(begin){
    data.assign(n, vt());

    for(int i=0;i<n;++i) {
		data[i].reserve(21); // 100w用21即可
		data[i].emplace_back(i, i);
	}

	for(int j=1,t;(t=1<<j)<=n;++j){
        for(int i=0;i+t<=n;++i){
			const auto & prv = data[i][j-1];
			const auto & nxt = data[i+(t>>1)][j-1];

			auto first = *(begin + prv.first) <= *(begin + nxt.first) ? prv.first : nxt.first;
			auto second = *(begin + nxt.second) <= *(begin + prv.second) ? prv.second : nxt.second;

			data[i].emplace_back(first, second);
		} 
	}

	return;
}

/// 查询[s, e]区间的极小极大值所在的下标，即距离构造函数begin的偏移量
/// 索引从0开始
T query(int s, int e)const{
    int k = static_cast<int>(log2((double)(e - s + 1)));
	const auto & p1 = data[s][k];
	const auto & p2 = data[e-(1<<k)+1][k];
    return {
        *(head + p1.first) <= *(head + p2.first) ? p1.first : p2.first,
		*(head + p2.second) <= *(head + p1.second) ? p1.second : p2.second 
	};
}


};

class Solution {
using llt = long long;
public:
    long long maximumProduct(vector<int>& nums, int m) {
        if(1 == m){
            llt ans = (llt)(nums[0]) * nums[0];
            for(auto i : nums){
                auto tmp = (llt)(i) * (llt)(i);
                if(ans < tmp) ans = tmp;
            }
            return ans;
        }

        int n = nums.size();

        unique_ptr<llt> ans = nullptr;
        SparseTable<> st(nums.begin(), n);
        for(int i=m-1;i<n;++i){
            auto right = i - (m - 1);
            auto p = st.query(0, right);
            auto v = (llt)nums[i];
            auto t0 = v * nums[p.first];
            if(nullptr == ans){
                ans = make_unique<llt>(t0);
            }else if(*ans < t0){
                *ans = t0;
            }
            auto t1 = v * nums[p.second];
            if(*ans < t1) *ans = t1;
        }
        return *ans;
    }
};